/**
 * 
 */
package leetCode;

import java.util.HashMap;

/**
 * @author zhong
 *
 */
public class UniquePathsIII {
	public int uniquePathsIII(int[][] grid) {
		int n = grid.length, m = grid[0].length;
		StringBuilder sBuilder = new StringBuilder(n * m);
		for (int i = 0; i < n * m; i++) {
			sBuilder.append("0");
		}
		int[][] findTarg = find(grid);
		return digui(findTarg[0], grid, sBuilder);
	}

	private int[][] find(int[][] grid) {
		int[] start = new int[2];
		int[] end = new int[2];
		for (int i = 0; i < grid.length; i++) {
			for (int j = 0; j < grid[0].length; j++) {
				if (grid[i][j] == 1) {
					start = new int[] { i, j };
				} else if (grid[i][j] == 2) {
					end = new int[] { i, j };
				}
			}
		}
		return new int[][] { start, end };
	}

	int[][] dirs = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };

	HashMap<String, Integer> point_status_res = new HashMap<>();

	private int digui(int[] cur, int[][] grid, StringBuilder sBuilder) {
		if (grid[cur[0]][cur[1]] == 2) {
			if (checkVisit(sBuilder, grid))
				return 1;
			else {
				return 0;
			}
		}
		String pos_visited = toStr(cur, sBuilder);// 備忘錄
		if (point_status_res.containsKey(pos_visited)) {
			return point_status_res.get(pos_visited);
		}
		int res = 0;
		for (int[] dir : dirs) {
			int[] neib = { cur[0] + dir[0], cur[1] + dir[1] };
			if (canVisit(neib, grid) && !visited(sBuilder, neib[0], neib[1], grid.length)) {
				StringBuilder newStatus = new StringBuilder(sBuilder);
				newStatus.setCharAt(toPos(neib[0], neib[1], grid.length), '1');
				int the_res = digui(neib, grid, newStatus);
				res += the_res;
			}
		}
		point_status_res.put(pos_visited, res);
		return res;
	}

	private boolean checkVisit(StringBuilder sBuilder, int[][] grid) {
		for (int i = 0; i < grid.length; i++) {
			for (int j = 0; j < grid[0].length; j++) {
				if (grid[i][j] == 0) {
					if (visited(sBuilder, i, j, grid.length)) {
						return false;
					}
				}
			}
		}
		return true;
	}

	private boolean visited(StringBuilder sBuilder, int i, int j, int length) {
		return sBuilder.charAt(toPos(i, j, length)) != '1';
	}

	private int toPos(int i, int j, int length) {
		return i * length + j;
	}

	private boolean canVisit(int[] neib, int[][] grid) {
		return neib[0] > -1 && neib[1] > -1 && neib[0] < grid.length && neib[1] < grid[0].length
				&& grid[neib[0]][neib[1]] != -1;
	}

	private String toStr(int[] cur, StringBuilder sBuilder) {
		return toStr(cur) + ":" + sBuilder;
	}

	private String toStr(int[] cur) {
		return cur[0] + "_" + cur[1];
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[][] A = { { 1, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 2, -1 } };
		System.out.println(new UniquePathsIII().uniquePathsIII(A));
	}

}
